package com.chj.leetcode.tijie900to950;

import java.util.HashSet;
import java.util.Set;

public class Code906_SuperPalindromes {
	public static int superpalindromesInRange(String L, String R) {
		long left = Long.parseLong(L);
		long right = Long.parseLong(R);
		long l = (long) Math.sqrt(left);
		long r = (long) Math.sqrt(right);

		int res = 0;
		while (l <= r) {
			String cur = genpalindrome(Long.toString(l));
			long sub = Long.parseLong(cur);
			long superCur = sub * sub;

			if (superCur > right) {
				break;
			}

			if (superCur >= left && ispalindrome(Long.toString(superCur))) {
//				System.out.println(sub + ": " + superCur);
				res++;
			}

			String subStr = nearestPalindromicMoreLower(Long.toString(sub));
			l = Long.parseLong(subStr);
		}

		return res;
	}

	public static boolean ispalindrome(String s) {
		int i = 0, j = s.length() - 1;
		while (i < j) {
			if (s.charAt(i) != s.charAt(j)) {
				return false;
			}
			i++;
			j--;
		}
		return true;
	}

	// 根据数字的前一半，生成奇数或者偶数的回文数字
	public static String genpalindrome(String n) {
		int len = n.length();
		String sub = n.substring(0, (len + 1) / 2);
		int prefix = Integer.parseInt(sub);
		String pre = String.valueOf(prefix);
		String tail = reverse(pre);
		String str = pre + ((len & 1) == 1 ? tail.substring(1) : tail);
		return str;
	}

	public static String nearestPalindromicMoreLower(String n) {
		int len = n.length();
		long num = Long.parseLong(n);
		long res = Integer.MAX_VALUE;
//			long minDiff = Long.MAX_VALUE;

		Set<Long> s = new HashSet<>();
		s.add((long) (Math.pow(10, len) + 1));
		s.add((long) (Math.pow(10, len - 1) - 1));
		String sub = n.substring(0, (len + 1) / 2);
		int prefix = Integer.parseInt(sub);
		for (long i = -1; i <= 1; ++i) {
			String pre = String.valueOf(prefix + i);
			String tail = reverse(pre);
			String str = pre + ((len & 1) == 1 ? tail.substring(1) : tail);
			s.add(Long.parseLong(str));
		}

		for (long a : s) {
			if (a > num) {
				res = Math.min(res, a);
			}
		}

//			s.remove(num);
//			for (long a : s) {
//				long diff = Math.abs(a - num);
//				if (diff < minDiff) {
//					minDiff = diff;
//					res = a;
//				} else if (diff == minDiff) {
//					res = Math.min(res, a);
//				}
//			}
		return String.valueOf(res);
	}

	public static String reverse(String str) {
		char[] chars = str.toCharArray();
		String reverse = "";
		int len = chars.length;
		for (int i = len - 1; i >= 0; i--) {
			reverse += chars[i];
		}
		return reverse;
	}

	public static void main(String[] args) {
		System.out.println(superpalindromesInRange("4", "1000"));
		System.out.println(superpalindromesInRange("11695", "23815"));
		System.out.println(superpalindromesInRange("1020762146323", "142246798855636"));
	}
}
